1623C - Balanced Stone Heaps - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+10;

int n;
vector<int> a(N);

bool func(int num){
    vector<int> v(a.begin(), a.begin()+n);
    for (int i = n - 1; i >= 2; i--)
    {
        if(v[i] < num) return false;

        int pp = min(a[i], (v[i]-num))/3;
        v[i]-=3*pp;
        v[i-1]+=pp;
        v[i-2]+=2*pp;
    }

    // for (int i = 0; i < n; i++)
    // {
    //     cout<<v[i]<<" ";
    // }
    // cout<<endl;

    if(v[0]>=num && v[1]>=num) return true;
    else return false;
    

}

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        for (int i = 0; i < n; i++)
        {
            cin>>a[i];
        }

        int lo=0, hi=1e9, mid;
        while (hi-lo>1)
        {
            mid=(hi+lo)/2;
            if(func(mid)) lo=mid;
            else hi=mid-1;
        }
        if(func(hi)) cout<<hi<<endl;
        else cout<<lo<<endl;
        
    }
    return 0;
}